package lc.q1_50;

import java.util.ArrayList;
import java.util.List;

public class Q50 {

    public double myPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        } else if (n == 1) {
            return x;
        } else if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                return (1/x) * myPow(x, n + 1);
            }
            return myPow(1 / x, -n);
        } else {
            int k = n;
            List<Integer> list = new ArrayList<>();
            while (k != 0) {
                list.add(k);
                k = k / 2;
            }
            double[] dps = new double[list.size()];
            dps[0] = x;
            for (int i = list.size() - 1; i >= 1; i--) {
                final Integer v = list.get(i);
                final Integer v2 = list.get(i - 1);
                dps[list.size() - i] = dps[list.size() - i -1] * dps[list.size() - i -1];
                if (v2 - v * 2 == 1) {
                    dps[list.size() - i] *= x;
                }
            }

            return dps[dps.length - 1];
        }
    }

    public static void main(String[] args) {
        final Q50 q50 = new Q50();
        final double v = q50.myPow(1.00000, Integer.MAX_VALUE);
        System.out.println(v);
    }

}
